from typing import List

class Solution:
    def mergeAlternately(self, word1: str, word2: str) -> str:
        n = len(word1)
        m = len(word2)
        i = 0
        j = 0
        lis = []
        length = max(n, m)
        while i < n or j < m:
            if i < n:
                lis.append(word1[i])
                i += 1
            if j < m:
                lis.append(word2[j])
                j += 1
        return "".join(lis)
'''
复杂度分析
时间复杂度：O(m+n)，其中 m 和 n 分别是字符串 word1和 word 2的长度。
空间复杂度：O(1) 或 O(m+n)。如果使用的语言支持可修改的字符串，
那么空间复杂度为 O(1)，否则为 O(m+n)。注意这里不计入返回值需要的空间。
'''

# word1 = "ab"
# word2 = "pqrs"
word1 = "abcd"
word2 = "pq"
print(Solution().mergeAlternately(word1, word2))